\section{Depth-two superconcentrators}
\label{sec:superconcentrator}

Consider a graph $G=(V,M,W,E)$ with three sets of vertices $V$, $M$
and $W$, where $|V|, |W|=n$, and all edges in $E$ go from $V$ to $M$
or $M$ to $W$.  Such a graph is called a depth-two
$n$-superconcentrator if for every $k \in \{1,2,\ldots,n\}$ and every
pair of subsets $S \subseteq V$ and $T \subseteq W$, each of size $k$,
there are $k$ vertex disjoint paths from $S$ to $T$.

We reprove two known lower bounds for depth-two superconcentrators:
the first one is a lower bound on the number of edges
(Theorem~\ref{thm:superconcentrator.lb}) shown in~\cite{RT} which we
reprove here using Theorem~\ref{thm:necessary.symmetric}; the second
one is a tradeoff result between the number of edges going from $V$ to
$M$ and the number of them going from $M$ to $W$
(Theorem~\ref{thm:superconcentrator.tradeoff}) shown in~\cite{DR}
which we reprove using Theorem~\ref{thm:necessary.asymmetric}.

\begin{theorem}[Radhakrishnan and Ta-Shma~\cite{RT}]
\label{thm:superconcentrator.lb}
If the graph $G=(V,M,W,E)$ is a depth-two $n$-superconcentrator, then
$|E(G)| = \Omega(n \frac{(\log n)^2}{\log\log n})$.
\end{theorem}

\begin{proof}
This proof is similar to the one used in \cite{RT}, but the use of
Theorem~\ref{thm:necessary.symmetric} makes the calculations
modular. Assume that the number of edges in a depth-two
$n$-superconcentrator $G$ is at most $(B/100) n \frac{(\log
  n)^2}{\log\log n}$, where $B$ is the constant in
Theorem~\ref{thm:necessary.symmetric}. By increasing the number of
edges by a factor at most two, we assume that each vertex in $M$ has
the same number of edges coming from $V$ and going to $W$. For a
vertex $v \in M$, let $\deg(v)$ denote the number of edges that come
from $V$ to $v$ (equivalently the number of edges that go from $v$ to
$W$). Let For $k \in [n^{1/4}, n^{3/4}]$, define
\begin{eqnarray*}
\High(k)   &=& \{v \in M: \deg(v) \geq \frac{n}{k} (\log n)^2 \}; \\
\Medium(k) &=& \{v \in M: \frac{n}{k} (\log n)^{-2} \leq \deg(v) 
                          < \frac{n}{k} (\log n)^2 \}; \\
\Low(k)    &=& \{v \in M: \deg(v) < \frac{n}{k} (\log n)^{-2} \}.
\end{eqnarray*}

\begin{claim}
For each $k \in [n^{1/4}, n^{3/4}]$, the number of edges incident on
$\Medium(k)$ is at least $\frac{B}{2} n \log n$.
\end{claim}
Fix a $k \in [n^{1/4},n^{3/4}]$. First observe that $|\High(k)| < k$,
for otherwise, the number of edges in $G$ would already exceed $n
(\log n)^2$, contradicting our assumption.  Thus, every pair of
subsets $S \subseteq V$ and $T \subseteq W$ of size $k$ each has a
common neighbour in $\Medium(k) \cup \Low(k)$. We are now in a
position to move to the setting of
Theorem~\ref{thm:necessary.symmetric}. For each vertex $v \in
\Medium(k) \cup \Low(k)$, consider the complete bipartite graph
between its in-neighbours in $V$ and out-neighbours in $W$.  The
analysis above implies that the union of these graphs is a bipartite
graph between $V$ and $W$ that has no independent set of size $k
\times k$. For $v \in \Medium(k) \cup \Low(k)$, let $\alpha_v =
\frac{\deg(v)}{n/k}$. Using Theorem~\ref{thm:necessary.symmetric}, it
follows that
\begin{equation}
\sum_{v \in \Medium(k) \cup \Low(k): \alpha_v \leq 1} \alpha_v^2 + \sum_{v \in \Medium(k) \cup \Low(k): \alpha_v > 1} \alpha_v \geq B k \log n.
\end{equation}
For $\alpha_v \leq 1$, $\alpha_v^2 \leq \alpha_v$ and thus we can
replace $\alpha_v^2$ by $\alpha_v$ when $(\log n)^{-2} \leq
\alpha_v \leq 1$ and conclude
\begin{equation}
\label{eq:fixedk}
\sum_{v \in \Low(k)} \alpha_v^2 + \sum_{v \in \Medium(k)} \alpha_v \geq B k \log n.
\end{equation}
One of the two terms in the LHS is at least half the RHS. If
it is the first term then noting that $\alpha_v < (\log n)^{-2}$
for all $v \in \Low(k)$, we obtain
\begin{eqnarray*}
\sum_{v \in \Low} \deg(v) & = & (n/k) \sum_{v \in \Low} \alpha_v \\
                        &\geq& (n/k) (\log n)^2 \sum_{v \in \Low} \alpha_v^2 \\
                        &\geq& \frac{B}{2} n (\log n)^3,
\end{eqnarray*}
Since the left hand side is precisely the number of edges entering $\Low(k)$,
this contradicts our assumption that $G$ has few edges. So, it must be that the 
second term in the LHS of (\ref{eq:fixedk}) is at least 
$\frac{B}{2} k \log n$. Then, the number of edges incident on $\Medium(k)$
is
\[ \sum_{v \in \Medium} \deg(v) = (n/k) \sum_{v \in \Medium} \alpha_v \geq \frac{B}{2} n \log n. \]
This completes the proof of the claim.

Now, consider values of $k$ of the form $n^{1/4} (\log n)^{4i}$ in the
range $[n^{1/4}, n^{3/4}]$. Note that there are at least
$(\frac{1}{10})\log n / \log \log n$ such values of $k$ and the sets
$\Medium(k)$ for these values of $k$ are disjoint. By the claim above,
each such $\Medium(k)$ has at least $\frac{B}{2} n \log n$ edges
incident on it, that is $G$ has a total of at least $\frac{B}{20} n
\frac{(\log n)^2}{\log \log n}$ edges, again contradicting our
assumption.
\end{proof}


\begin{theorem}[Dutta and Radhakrishnan~\cite{DR}]
\label{thm:superconcentrator.tradeoff}
If the graph $G=(V,M,W,E)$ is a depth-two $n$-superconcentrator with
average degree of nodes in $V$ and $W$ being $a$ and $b$ respectively
and $a \leq b$, then
\[ a \log\left(\frac{a + b}{a}\right) \log b = \Omega(\log^2 n). \]
\end{theorem}

\begin{proof}
We may assume that $b > \log n$, otherwise the total number of edges
in $G$ is at most $2n\log n$ which contradicts
Theorem~\ref{thm:superconcentrator.lb} proved earlier. We may also
assume that $b < (\log n)^{\frac{1}{10}}$, otherwise the theorem can
be easily seen to be true.  For a vertex $v \in M$, let $\deg_V(v)$
denote the number of edges that come from $V$ to $v$ and $\deg_W(v)$
denote the number of edges that go from $v$ to $W$. We will assume
that the ratio $\frac{\deg_V(v)}{\deg_W(v)}$ is equal to $\frac{a}{b}$
for each vertex $v \in M$. This is without loss of generality as we
can make the ratio $\frac{\deg_V(v)}{\deg_W(v)}$ equal to
$\frac{a}{b}$ by increasing the number of edges from $V$ to $v$ (if
$\frac{\deg_V(v)}{\deg_W(v)}$ is smaller) or increasing the number of
edges from $v$ to $W$ (if the ratio is larger), and this process does
not increase the number of edges between $V$ and $M$ or between $M$
and $W$ more than by a factor two. (We ignore the rounding issues as
they are not important.)

For $k \in [n^{1/4}, n^{3/4}]$, define
\begin{eqnarray*}
\High(k)   &=& \{v \in M: \deg(v) \geq \frac{n}{k} b^2 \}; \\
\Medium(k) &=& \{v \in M: \frac{n}{k} b^{-2} \leq \deg(v) 
                          < \frac{n}{k} b^2 \}; \\
\Low(k)    &=& \{v \in M: \deg(v) < \frac{n}{k} b^{-2} \}.
\end{eqnarray*}

We consider values of $k$ of the form $n^{1/4} b^{4i}$ in the range
$[n^{1/4},n^{3/4}]$.  There are at least $L = \frac{\log n}{10 \log
  b}$ such values of $k$ and the sets $\Medium(k)$ for these values of
$k$ are disjoint. Thus out of these
values of $k$, we can find one, say $k_0$, such that the number
of edges from $V$ to $\Medium(k_0)$ is at most $\frac{an}{L}$. 

We observe that $|\High(k_0)| < k_0$, otherwise the number of edges
between $M$ and $W$ would be at least $b^2 n > bn$ which is a
contradition. Thus every pair of subsets $S \subseteq V$ and $T
\subseteq W$ of size $k$ each has a common neighbour in $\Medium(k_0)
\cup \Low(k_0)$. For each vertex $v \in \Medium(k_0) \cup \Low(k_0)$,
consider the complete bipartite graph between the in-neighbours and
out-neighbours of $v$.  The union of these graphs is a bipartite graph
between $V$ and $W$ that has no independent set of size $k \times
k$. For $v \in \Medium(k_0) \cup \Low(k_0)$, let $\alpha_v =
\frac{\deg_V(v)}{n/k_0}$ and $\beta_v = \frac{\deg_W(v)}{n/k_0}$. It
follows from Theorem~\ref{thm:necessary.asymmetric} that
\begin{equation}
\label{eq:averagek}
\sum_{v\in \Low(k_0)} \alpha_v \beta_v + \sum_{v \in \Medium(k_0)} (\alpha_v + \beta_v) \ent(\frac{\alpha_v}{\alpha_v + \beta_v}) \geq D k_0 \log n.
\end{equation}
where $D$ is the constant from Theorem~\ref{thm:necessary.asymmetric}.
One of the two terms in the LHS is at least half the RHS.
If it is the first term, noting that $\beta_v < b^{-2}$
for all $v \in \Low(k_0)$, we obtain
\begin{eqnarray*}
\sum_{v \in \Low(k_0)} \deg_V(v) & = & (n/k_0) \sum_{v \in \Low(k_0)} \alpha_v \\
                              &\geq& (n/k_0) b^2 \sum_{v \in \Low(k_0)} \alpha_v \beta_v \\
                              &\geq& \frac{D}{2} n \log n b^2  \\
                              &\geq& \frac{D}{2} n (\log n)^3
\end{eqnarray*}
Since the left hand side is precisely the number of edges entering
$\Low(k_0)$, we get $a \geq \frac{D}{2} (\log n)^3$ which proves the
theorem.  If the second term in the LHS of (\ref{eq:averagek}) is at
least $\frac{D}{2} k_0 \log n$, we get
\[ \sum_{v \in \Medium(k_0)} (\alpha_v + \beta_v) \ent(\frac{\alpha_v}{\alpha_v + \beta_v}) \geq \frac{D}{2} k_0 \log n. \]
Simplifying we get
\[ \sum_{v \in \Medium(k_0)} \left(\alpha_v \log\left(\frac{\alpha_v + \beta_v}{\alpha_v}\right) 
   + \beta_v \log \left(\frac{\alpha_v + \beta_v}{\beta_v}\right) \right) \geq \frac{D}{2} k_0 \log n. \]
We know that
\[ \left(\frac{\alpha_v + \beta_v}{\beta_v}\right)^{\beta_v} = \left(1 + \frac{\alpha_v}{\beta_v}\right)^{\beta_v} \leq \exp(\alpha_v), \]
which means
\[ \beta_v \log \left(\frac{\alpha_v + \beta_v}{\beta_v}\right) \leq \frac{\alpha}{\ln 2}. \]
Noting $\frac{\alpha_v + \beta_v}{\alpha_v} = \frac{a + b}{a}$, we have
\[ \sum_{v \in \Medium(k_0)} \alpha_v \log\left(\frac{a + b}{a} + \frac{1}{\ln 2} \right) \geq \frac{D}{2} k_0 \log n. \]
Since $a \leq b$, $\frac{a + b}{a} \geq 1$ and we conclude
\[ \sum_{v \in \Medium(k_0)} \alpha_v \log\left(\frac{a + b}{a} \right) = \Omega(k_0 \log n). \]
The number of edges from $V$ to $\Medium(k_0)$ is precisely 
\[ \sum_{v \in \Medium(k_0)} \deg_V(v) = (n/k_0) \sum_{v \in \Medium(k_0)} \alpha_v. \] 
But we know that there are at most $\frac{an}{L}$ edges from $V$ to
$\Medium(k_0)$. Thus
\[ \frac{ak_0}{L} \log \left(\frac{a + b}{a}\right) = \Omega(k_0 \log n), \]
which implies
\[ a \log\left(\frac{a + b}{a}\right) \log b = \Omega(\log^2 n). \]
\end{proof}

